{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个二叉树，返回它的 后序 遍历。\n",
    "\n",
    "示例:\n",
    "```\n",
    "输入: [1,null,2,3]  \n",
    "   1\n",
    "    \\\n",
    "     2\n",
    "    /\n",
    "   3 \n",
    "\n",
    "输出: [3,2,1]\n",
    "```\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import TreeNode\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            helper(root.left)\n",
    "            helper(root.right)\n",
    "            ans.append(root.val)\n",
    "        helper(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "迭代，模拟递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import TreeNode\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack, output = [root, ], []\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            output.append(root.val)\n",
    "            if root.left is not None:\n",
    "                stack.append(root.left)\n",
    "            if root.right is not None:\n",
    "                stack.append(root.right)\n",
    "                \n",
    "        return output[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[3, 2, 1]"
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "source": [
    "t = TreeNode.create([1, None, 2, 3])\n",
    "Solution().postorderTraversal(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[2, 3, 1]"
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "source": [
    "# 前序遍历和后序遍历是互逆的\n",
    "t = TreeNode.create([1, 2, 3])\n",
    "Solution().postorderTraversal(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}